package util;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileWriter;
import java.io.IOException;
import java.io.InputStreamReader;

public class Combination {

	private static String SWAP = "swap.dat";
	private int init[];
	private int end[];
	private int n;
	private int m;
	private BufferedReader in;

	public BufferedWriter output;

	public Combination() throws IOException {
		in = new BufferedReader(new InputStreamReader(System.in));
		output = new BufferedWriter(new FileWriter(SWAP));
		n = getInput("Please enter the totle number n ( that is 1~n and n>0 ) : ");
		m = getInput("Please enter the number of integers to be selected m ( 0<m<=n ) : ");
		while (n < m)
			m = getInput("Wrong!! Attention m<=n !!\n Please enter the number of integers to be selected m ( 0<m<=n ) : ");
		init = new int[n];
		for (int i = 1; i <= n; i++)
			init[i - 1] = i;
		end = new int[m];
	}

	public Combination(int n, int m) throws IOException {
		output = new BufferedWriter(new FileWriter(SWAP));
		this.n = n;
		this.m = m;
		init = new int[n];
		for (int i = 1; i <= n; i++)
			init[i - 1] = i;
		end = new int[m];
	}

	// recursion method
	public void choose1(int k, int l) throws IOException {
		if (l == m) {
			for (int i = 0; i < m; i++) {
				// System.out.print(end[i] + " ");
				output.write(end[i] + " ");
			}
			// System.out.println();
			output.write('\n');
		} else if (n - k == m - l) {
			for (int i = 0; i < m - l; i++)
				end[l + i] = init[k + i];
			for (int i = 0; i < m; i++) {
				// System.out.print(end[i] + " ");
				output.write(end[i] + " ");
			}
			// System.out.println();
			output.write('\n');
		} else {
			end[l] = init[k];
			choose1(k + 1, l + 1);
			choose1(k + 1, l);
		}
	}

	// non-recursion method
	public void choose2() {
		int trace = 0;
		for (int i = 0; i < n;) {
			if (n - i == m - trace) {
				for (int j = 0; j < m - trace; j++)
					end[trace + j] = init[i + j];
				for (int j = 0; j < m; j++)
					System.out.print(end[j] + " ");
				System.out.println();
				if (trace == 0)
					break;
				i = end[--trace];
			} else if (trace == m) {
				for (int j = 0; j < m; j++)
					System.out.print(end[j] + " ");
				System.out.println();
				i = end[--trace];
			} else
				end[trace++] = init[i++];
		}
	}

	public int getInput(String info) {
		int temp = 0;
		System.out.print("\n" + info);
		try {
			temp = Integer.parseInt(in.readLine());
		} catch (Exception e) {
			System.out.println("Wrong!! Input again!!");
			return getInput(info);
		}
		if (temp <= 0) {
			System.out.println("\nWrong!! Should grater than 0 !");
			return getInput("Enter again : ");
		} else
			return temp;
	}

	public static void main(String arf[]) throws IOException {
		Combination demo = new Combination();
		// int[] suites = { 7, 81, 9 };
		// demo.permute(suites);
		// System.out.println(demo.mem);
		System.out.println("--------recursion method--------");
		demo.choose1(0, 0);
		demo.output.close();
		System.out.println("--------non-recursion method--------");
		demo.choose2();
	}
}
